package 板子;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/8 16:12
 */
public class UnionFindSets {
    /*
    左程云的 Map 版本的并查集也可以参考一下！
     用数组实现一个并查集
     这个板子要熟悉
     */


    public static class UnionFind {


        private int parent[]; // parent[i] : 表示的是 i 的 **直接** 父亲是 parent[i];

        private int help[]; // 压缩路径的一个辅助数组

        private int size[]; //  i 所在集合的大小 ,  先 find(i) 找到 ip 然后 size[ip] 这才是最正确的做法

        private int sets; // 一共有多少个 没有任何 **交集** 的集合!


        public UnionFind() {

        }

        public UnionFind(int N) {
            this.parent = new int[N];
            this.help = new int[N];
            this.size = new int[N];
            this.sets = N;
            for (int i = 0; i < N; i++) {
                parent[i] = i; // 初始化的时候, 自己是自己的父亲
                size[i] = 1; // 每个点 自己单独是一个集合
            }
        }

        // 并
        public void union(int i, int j) { // 将 i 所在的集合 和 j 所在的 集合 进行 合并成为一个 集合, 那么sets 就要减少!
            int i_parent = find(i), j_parent = find(j);
            if(i_parent != j_parent){ // 不在一个集合才进行合并, 如果在一个集合,那还合并个毛线!
                int i_size = size[i_parent];
                int j_size = size[j_parent];

                // 很容易搞混, 别出错!
                if(i_size >= j_size){ // 将 j所在集合 合并到 i
                    parent[j_parent] = i_parent;
                    size[i_parent] = i_size + j_size;
                }else{
                    parent[i_parent] = j_parent;
                    size[j_parent] = i_size + j_size;
                }
                sets--;
            }
        }
        // 并 的另外一种写法 (直接 不优化了) , 就是 i, j 的集合谁大谁小都不管了, 实现起来比较简单!
        public void unionNoGood(int i, int j) { // 将 i 所在的集合 和 j 所在的 集合 进行 合并成为一个 集合, 那么sets 就要减少!
            int i_parent = find(i), j_parent = find(j);
            if(i_parent != j_parent){
                parent[i_parent] = j_parent;
                size[j_parent] += size[i_parent];
                sets--;
            }
        }



        // 查
        public int find(int cur) { //  当一个点的上级, 是自己的时候,那这个点就是老大了 boss! 就按照这个思想来去find, find的过程中,要进行一个路径的压缩!
            int index = 0;
            while (cur != parent[cur]) { // 如果cur 的父亲不是自己, 说明还没来到顶层!
                cur = parent[cur];
                help[index++] = cur;
            }

            while (--index >= 0) { // 开始进行路径压缩, 也就是 把 沿途收集的 节点 help的中的点, 指向 cur , 把 长链 扁平化!
                parent[index] = cur;
            }
            return cur;
        }

        // 查 递归版本 这个递归还挺 考验思维的!
        public int find_recursion(int cur){
            if(parent[cur] == cur){
                return cur;
            }
            // 先 递归 再 压缩路径    -- 递归的小技巧
            int boss = find_recursion(parent[cur]);
            // 压缩路径
            parent[cur] = boss;
            return boss;
        }





        // 判断给出的 两个点,在不在同一个集合
        public boolean isSameSet(int i,int j){
            return find(i) == find(j);
        }


        // 返回没有交集的集合的数量
        public int sets(){
            return  sets;
        }

    }





    /*
     并查集的 极简 Version

     但是个人建议  把 Size 数组 留下,
     如果 某个题涉及到 求  i 所在集合的大小, 这样的话, 通过这个 size 数组会 比较 好算一些!
     */

    class UnionFindSimplify{
        private int []paernt; //

        private int []size; // i 所在集合的大小

        private int sets; // 一共有多少个 没有任何 **交集** 的集合 (也就是有多少个 连通分量)


        /*
         初始化的版本 I
         又增加了一个 add方法
         */

        public UnionFindSimplify(int n,int nothing){
            paernt = new int[n];
            size = new int[n];
        }

        /*
         有些题型 的话, 这样的初始化会好一些!
         */
        public void add(int x){
            paernt[x] = x;
            size[x] = 1;
            // 这个 可别忘了写
            sets++;
        }





        /*
         直接 一步到位的初始化
         */
        public UnionFindSimplify(int n){
            paernt = new int[n];
            size = new int[n];
            sets = n;
            for(int  i = 0;i < n;i++){
                paernt[i] = i;
//                size[i] = 1;
            }
        }

        public int find(int cur){
            if(cur == paernt[cur]){ // basecase  find  boss
                return cur;
            }
            return paernt[cur] = find(paernt[cur]);
        }


        public void union(int i,int j){
            int iP = find(i), jP = find(j);
            if(iP != jP){
                paernt[iP] = jP;
//                size[jP] += size[iP];
                sets--;
            }
        }

        public int sets(){
            return sets;
        }
    }


}
